<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>堆实现优先队列</title>
  </head>
  <body>
    <script type="text/javascript">
      // 用最大堆来实现最大优先队列
      function PriorityQueue() {
        this.array = []; // 存储队列元素
        this.enqueue = enqueue; // 入队
        this.dequeue = dequeue; // 出队
        this.upAdjust = upAdjust; // 堆“上浮”操作
        this.downAdjust = downAdjust; // 堆“下沉”操作
      }

      /*
       * 入队
       * @param key 入队元素
       */
      function enqueue(key) {
        this.array.push(key);
        this.upAdjust();
      }

      /*
       * 出队
       */
      function dequeue() {
        // 获取堆顶元素
        const head = this.array[0];
        // 让最后一个元素移动到堆顶
        this.array[0] = this.array[this.array.length - 1];
        this.downAdjust();
        return head;
      }

      /*
       * “上浮”调整
       */
      function upAdjust() {
        let childIndex = this.array.length - 1;
        let parentIndex = Math.floor((childIndex - 1) / 2);
        // temp 保存插入的叶子节点值，用于最后的赋值
        const temp = this.array[childIndex];
        while (childIndex > 0 && temp > this.array[parentIndex]) {
          // 无须真正交换，单向赋值即可
          this.array[childIndex] = this.array[parentIndex];
          childIndex = parentIndex;
          parentIndex = Math.floor(parentIndex / 2);
        }
        this.array[childIndex] = temp;
      }

      /*
       * “下沉”调整
       */
      function downAdjust() {
        // temp 保存父节点的值，用于最后的赋值
        let parentIndex = 0;
        const temp = this.array[parentIndex];
        let childIndex = 1;

        while (childIndex < this.array.length - 1) {
          // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
          if (
            childIndex + 1 < this.array.length - 1 &&
            this.array[childIndex + 1] > this.array[childIndex]
          ) {
            childIndex++;
          }
          // 如果父节点大于任何一个孩子的值，直接跳出
          if (temp >= this.array[childIndex]) break;
          // 无须真正交换，单向赋值即可
          this.array[parentIndex] = this.array[childIndex];
          parentIndex = childIndex;
          childIndex = 2 * childIndex + 1;
        }
        this.array[parentIndex] = temp;
      }

      const priorityQueue = new PriorityQueue();
      priorityQueue.enqueue(3);
      priorityQueue.enqueue(5);
      priorityQueue.enqueue(10);
      priorityQueue.enqueue(2);
      priorityQueue.enqueue(7);
      console.log(priorityQueue.array);
      console.log('出队元素：' + priorityQueue.dequeue()); // 出队元素：10
      console.log('出队元素：' + priorityQueue.dequeue()); // 出队元素：7
    </script>
  </body>
</html>
